#include <stdio.h>
#include <stdlib.h>

typedef enum
{
    false,true
}
bool;
#define INFINITY 1000000
#define MaxVertexNum 10  /* maximum number of vertices */
typedef int Vertex;      /* vertices are numbered from 0 to MaxVertexNum-1 */
typedef int WeightType;

typedef struct GNode*PtrToGNode;
struct GNode
{
    int        Nv;
    int        Ne;
    WeightType G[MaxVertexNum][MaxVertexNum];
};
typedef PtrToGNode  MGraph;

MGraph ReadG(); /* details omitted */

void ShortestDist(MGraph Graph,int dist[],int count[],Vertex S);

int main()
{
    int    dist[MaxVertexNum],count[MaxVertexNum];
    Vertex S,V;
    MGraph G=ReadG();
    
    scanf("%d",&S);
    ShortestDist(G,dist,count,S);
    
    for(V=0;V<G->Nv;V++)
        printf("%d ",dist[V]);
    printf("\n");
    for(V=0;V<G->Nv;V++)
        printf("%d ",count[V]);
    printf("\n");
    
    return 0;
}

/* Your function will be put here */
void aaa(MGraph Graph,int dist[],int count[],Vertex S)
{
    for(Vertex i=0;i<Graph->Nv;++i)
        if(Graph->G[S][i]!=INFINITY)
        {
            int tmp=dist[S]+Graph->G[S][i];
            if(dist[i]==-1||tmp<dist[i])
            {
                count[i]=1;
                dist[i] =tmp;
                aaa(Graph,dist,count,i);
            }
            else if(tmp==dist[i])
            {
                count[i]+=1;
                aaa(Graph,dist,count,i);
            }
        }
}
void ShortestDist(MGraph Graph,int dist[],int count[],Vertex S)
{
    for(Vertex i=0;i<Graph->Nv;dist[i]=-1,count[i]=0,++i);
    dist[S]=0;
    count[S]=1;
    aaa(Graph,dist,count,S);
    
}